// 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
// 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
// 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

// 神奇的深度优先 没屁用！（我是傻子）
var maxValue = function (grid) {
    let m = grid.length, n = grid[0].length
    let root = new BiTree(0, 0, grid[0][0])
    let queue = [root], ptr = 0; // 根节点入队
    let tempmax = 0;
    let i = 0;
    // 遍历队列
    while (ptr < queue.length) {
        p = queue[ptr]
        if (p.val > tempmax) tempmax = p.val
        if (p.x < m && p.y < n) {
            if (p.x !== m - 1) {
                // 有重复节点
                if (p.x + 1 === queue[i].x && p.y === queue[i].y) {
                    // 取值大的
                    if (p.val + grid[p.x + 1][p.y] > queue[i].val)
                        queue[i].val = p.val + grid[p.x + 1][p.y]
                } else {
                    // 左孩子入队
                    let nodeLeft = new BiTree(p.x + 1, p.y, p.val + grid[p.x + 1][p.y])
                    p.left = nodeLeft
                    queue.push(nodeLeft)
                    i++
                }
            }
            if (p.y !== n - 1) {
                // 右孩子入队
                let nodeRight = new BiTree(p.x, p.y + 1, p.val + grid[p.x][p.y + 1])
                p.right = nodeRight
                queue.push(nodeRight)
                i++
            }
        }
        ptr++
    }
    return tempmax;
}
function BiTree(x, y, val) {
    this.left = null;
    this.right = null;
    this.val = val;
    this.x = x;
    this.y = y;
}

// 动态规划
var maxValueTwo = function (grid) {
    let m = grid.length, n = grid[0].length
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(i === 0 && j === 0) continue
            else if(i === 0 && j !== 0)  grid[i][j] += grid[i][j - 1]
            else if(i !== 0 && j === 0)  grid[i][j] += grid[i - 1][j]
            else grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1])
        }
    }
    return grid[m - 1][n - 1]
}
console.log(maxValueTwo([[1, 3, 1], [1, 5, 1], [4, 2, 1]]));
console.log(maxValueTwo([[1, 2],[4, 5]]));